<!DOCTYPE html>
<html>
  <head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  <meta name="description" content="tong.li&#39;s blog">
  <meta name="keyword" content="彤哥哥博客，95后技术爱好者,现就职于同程旅行/同程艺龙上海分公司，专注于互联网技术分享的平台。">
  
    <link rel="shortcut icon" href="/css/images/icon.png">
  
  <title>
    
      【数据结构与算法】高效的位运算 | 彤哥哥的博客
    
  </title>
  <link href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/highlight.js/9.12.0/styles/tomorrow-night.min.css" rel="stylesheet">
  
<link rel="stylesheet" href="/css/style.css">

  
  <script src="https://cdn.staticfile.org/jquery/3.2.1/jquery.min.js"></script>
  <script src="https://cdn.staticfile.org/geopattern/1.2.3/js/geopattern.min.js"></script>
  <script src="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.js"></script>
  
    
<script src="/js/qrious.js"></script>

  
  
  
  
    <!-- MathJax support START -->
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="https://cdn.staticfile.org/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <!-- MathJax support END -->
  


  
  
    
<script src="/js/local-search.js"></script>


<meta name="generator" content="Hexo 5.4.2"></head>
<div class="wechat-share">
  <img src="/css/images/logo.png" />
</div>
  <body>
    <header class="header fixed-header">
  <div class="header-container">
    <a class="home-link" href="/">
      <div class="logo"></div>
      <span>彤哥哥的博客</span>
    </a>
    <ul class="right-list">
      
        <li class="list-item">
          
            <a href="/" class="item-link">主页</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/series/" class="item-link">分类</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/tags/" class="item-link">标签</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/archives/" class="item-link">归档</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/project/" class="item-link">项目</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/about/" class="item-link">关于</a>
          
        </li>
      
      
        <li class="menu-item menu-item-search right-list">
    <a role="button" class="popup-trigger">
        <i class="fa fa-search fa-fw"></i>
    </a>
</li>
      
    </ul>
    <div class="menu">
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
    </div>
    <div class="menu-mask">
      <ul class="menu-list">
        
          <li class="menu-item">
            
              <a href="/" class="menu-link">主页</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/series/" class="menu-link">分类</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/tags/" class="menu-link">标签</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/archives/" class="menu-link">归档</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/project/" class="menu-link">项目</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/about/" class="menu-link">关于</a>
            
          </li>
        
      </ul>
    </div>
    
      <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
            <span class="search-icon">
                <i class="fa fa-search"></i>
            </span>
            <div class="search-input-container">
                <input autocomplete="off" autocapitalize="off"
                    placeholder="Please enter your keyword(s) to search." spellcheck="false"
                    type="search" class="search-input">
            </div>
            <span class="popup-btn-close">
                <i class="fa fa-times-circle"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>
    
  </div>
</header>

    <div id="article-banner">
  <h2>【数据结构与算法】高效的位运算</h2>
  <p class="post-date">2022-05-02</p>
  <div class="arrow-down">
    <a href="javascript:;"></a>
  </div>
</div>
<main class="app-body flex-box">
  <!-- Article START -->
  <article class="post-article">
    <section class="markdown-content"><h1 id="1-数据表示与进制转化"><a href="#1-数据表示与进制转化" class="headerlink" title="1. 数据表示与进制转化"></a>1. 数据表示与进制转化</h1><p>在了解位运算之前，我们先回顾一下进制的基础知识。</p>
<p>虽然我们日常生活中都是以十进制数来做计算处理的。但是在计算机世界中，机器都是以bit（比特位）0、1这样的二进制数来处理的。</p>
<h2 id="1-1-数据表示"><a href="#1-1-数据表示" class="headerlink" title="1.1 数据表示"></a>1.1 数据表示</h2><h3 id="1-1-1-十进制"><a href="#1-1-1-十进制" class="headerlink" title="1.1.1 十进制"></a>1.1.1 十进制</h3><ul>
<li><p>基数（radix）：10</p>
</li>
<li><p>数符: 0、1、2、3、4、5、6、7、8、9</p>
</li>
<li><p>进位规则：逢十进一</p>
</li>
<li><p>权(基数的i次幂)：10^i</p>
</li>
<li><p>形式表示符号：D(Decimal，缩写：Dec)</p>
</li>
</ul>
<p>十进制数1234.55，按照不同位置的数符及所在位置的权值，可表示为如下：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">十进制的1234.55 = 1 * (10^3) + 2 * (10^2) + 3 * (10^1) + 4 * (10^0) + 5 * (10^-1) + 5 * (10^-2)</span><br></pre></td></tr></table></figure>

<h3 id="1-1-2-二进制"><a href="#1-1-2-二进制" class="headerlink" title="1.1.2 二进制"></a>1.1.2 二进制</h3><ul>
<li><p>基数（radix）：2</p>
</li>
<li><p>数符: 0、1</p>
</li>
<li><p>进位规则：逢二进一</p>
</li>
<li><p>权(基数的i次幂)：2^i</p>
</li>
<li><p>形式表示符号：B(Binary，缩写：Bin)</p>
</li>
</ul>
<p>与十进制表示法相同，二进制数0110，按照不同位置的数符及所在位置的权值，可表示为如下：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">二进制的0110 = 0 * (2^3) + 1 * (2^2) + 1 * (2^1) + 0 * (2^0) = 十进制的6</span><br></pre></td></tr></table></figure>

<h3 id="1-1-3-八进制"><a href="#1-1-3-八进制" class="headerlink" title="1.1.3 八进制"></a>1.1.3 八进制</h3><ul>
<li><p>基数（radix）：8，即称八进制</p>
</li>
<li><p>数符: 0、1、2、3、4、5、6、7</p>
</li>
<li><p>进位规则：逢八进一</p>
</li>
<li><p>权(基数的i次幂)：8^i</p>
</li>
<li><p>形式表示符号：O(Octal，缩写：Oct)</p>
</li>
</ul>
<p>与十进制表示法相同，八进制数3502，按照不同位置的数符及所在位置的权值，可表示为如下：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">八进制的3502 = 3 * (8^3) + 5 * (8^2) + 0 * (8^1) + 2 * (8^0) = 十进制的1858</span><br></pre></td></tr></table></figure>

<h3 id="1-1-4-十六进制"><a href="#1-1-4-十六进制" class="headerlink" title="1.1.4 十六进制"></a>1.1.4 十六进制</h3><ul>
<li><p>基数（radix）：16，即称十六进制</p>
</li>
<li><p>数符: 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F</p>
</li>
<li><p>进位规则：逢十六进一</p>
</li>
<li><p>权(基数的i次幂)：16^i</p>
</li>
<li><p>形式表示符号：H(Hexadecimal，缩写：Hex)</p>
</li>
</ul>
<p>与十进制表示法相同，十六进制数16AF(A-F位可以按十进制的10-15处理)，按照不同位置的数符及所在位置的权值，可表示为如下：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">十六进制的16AF = 1 * (16^3) + 6 * (16^2) + A(可转化为十进制的10) * (16^1) + F(可转化为十进制的15) * (16^0) = 十进制的5807</span><br></pre></td></tr></table></figure>

<h2 id="1-2-进制转化"><a href="#1-2-进制转化" class="headerlink" title="1.2 进制转化"></a>1.2 进制转化</h2><h3 id="1-2-1-十进制与二进制转化"><a href="#1-2-1-十进制与二进制转化" class="headerlink" title="1.2.1 十进制与二进制转化"></a>1.2.1 十进制与二进制转化</h3><p>上述介绍二进制的时候，我们可以把二进制数转为为10进制数，那么十进制怎么去转化二进制数呢？</p>
<p>将十进制数转化为二进制数时，整数部分和小数部分分别转化，然后再合并。具体转化方法</p>
<ul>
<li><p><strong>整数转换方法：除2取余</strong></p>
</li>
<li><p><strong>小数转换方法:   乘2取整</strong></p>
</li>
</ul>
<p><img src="https://ltyeamin.github.io/imgs/2022/05/20220502144346.png"></p>
<p>二进制数转化成十进制数的方法是: <strong>将二进制数的每一位数乘以它的权，然后相加，即可求得对应的十进制的值</strong>。</p>
<p><img src="https://ltyeamin.github.io/imgs/2022/05/20220502150357.png"></p>
<h3 id="1-2-2-二进制与八进制转化"><a href="#1-2-2-二进制与八进制转化" class="headerlink" title="1.2.2 二进制与八进制转化"></a>1.2.2 二进制与八进制转化</h3><p>十进制数转化为八进制数与十进制转二进制数方法类似：<strong>十进制整数部分除8取余，十进制小数部分乘8取整。</strong></p>
<p>这里着重讲一下二进制转化为八进制，具体转换方法为：</p>
<p><strong>从小数点起，每三位二进制位分成一组(不足3位时，在小数点左边时左补0，在小数点右边时右补0)，然后写出每一组的等值八进制数，顺序排列起来就是所求的八进制数。</strong></p>
<p><img src="https://ltyeamin.github.io/imgs/2022/05/20220502145814.png"></p>
<h3 id="1-2-3-二进制与十六进制转化"><a href="#1-2-3-二进制与十六进制转化" class="headerlink" title="1.2.3 二进制与十六进制转化"></a>1.2.3 二进制与十六进制转化</h3><p>十进制数转化为十六进制数与十进制转二进制数方法类似：<strong>十进制整数部分除16取余，十进制小数部分乘16取整。</strong></p>
<p>由于一个16进制数可以用4位二进制数来表示，具体转换方法为：</p>
<p><strong>从小数点起，每四位二进制位分成一组(不足4位时，在小数点左边时左补0，在小数点右边时右补0)，然后写出每一组的等值十六进制数，顺序排列起来就是所求的十六进制数。</strong></p>
<p><img src="https://ltyeamin.github.io/imgs/2022/05/20220502150253.png"></p>
<h3 id="1-2-4-四种码制"><a href="#1-2-4-四种码制" class="headerlink" title="1.2.4 四种码制"></a>1.2.4 四种码制</h3><ul>
<li><p>原码：</p>
<ul>
<li><p>将数值直接转换为二进制数，首位为符号位，0表示正数，1表示负数</p>
</li>
<li><p>若机器字长为8，那么+1的原码为00000001，-1的原码为10000001</p>
</li>
<li><p>0的原码有两种：00000000和10000000</p>
</li>
</ul>
</li>
<li><p>反码</p>
<ul>
<li><p>正数的反码与其原码相同，负数的反码是在原码的基础上，除符号位不变，其余各位取反。</p>
</li>
<li><p>若机器字长为8，那么+1的反码为00000001，-1的反码为11111110</p>
</li>
<li><p>0的反码有两种：00000000和11111111</p>
</li>
</ul>
</li>
<li><p>补码</p>
<ul>
<li><p>正数的补码与其原码相同，负数的补码=负数的反码+1</p>
</li>
<li><p>若机器字长为8，那么+1的补码为00000001，-1的补码=-1的反码(11111110) + (00000001) = 11111111</p>
</li>
<li><p>0的补码只有1种形式，即00000000</p>
</li>
</ul>
</li>
<li><p>移码</p>
<ul>
<li><p>移码是在数x上增加一个偏移量来定义，如果机器字长为n，规定的偏移量为2^n-1(即2的n-1次方)</p>
</li>
<li><p>若机器字长为8，则偏移量为2^7，相当于给数x按位相加10000000</p>
</li>
<li><p>实际上，在偏移量为2^n-1的情况下，只要将补码的符号位取反便可得到相应的移码</p>
</li>
<li><p>0的移码只有唯一形式：10000000</p>
</li>
</ul>
</li>
</ul>
<p><strong>负数在计算机中是以其正值的补码形式表达。那么十进制的负数转化二进制位的方式为：获得原码后，最高位符号位不变，进行取反(反码)+1。得到的补码就是负数的二进制数。</strong></p>
<h3 id="1-2-5-常用数值"><a href="#1-2-5-常用数值" class="headerlink" title="1.2.5 常用数值"></a>1.2.5 常用数值</h3><p><img src="https://ltyeamin.github.io/imgs/2022/05/20220502151025.png"></p>
<p>上表为二进制、八进制、十六进制数的对应关系，我们需要牢记。</p>
<p>除此之外，我们要熟记2的几次幂，这样可以提升我们十进制与二进制转化速度，以8位的二进制示例：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">二进制:      0   0    0    0    0    0    0    0    </span><br><span class="line">十进制:    128  64   32   16    8    4    2    1</span><br></pre></td></tr></table></figure>

<h1 id="2-常见位运算"><a href="#2-常见位运算" class="headerlink" title="2. 常见位运算"></a>2. 常见位运算</h1><h2 id="2-1-与运算"><a href="#2-1-与运算" class="headerlink" title="2.1 与运算"></a>2.1 与运算</h2><p>与运算，又称为逻辑乘，常用表示：&amp;、AND、∩，两个逻辑全部为真，结果才能为真，只要有一个假，那么结果为假，示例：0101 &amp; 1100 = 0100。</p>
<h2 id="2-2-或运算"><a href="#2-2-或运算" class="headerlink" title="2.2 或运算"></a>2.2 或运算</h2><p>或运算，又称为逻辑加，常用表示：|、OR、∪，两个逻辑只要有一个为真，结果为真。若全部为假，那么结果为假。示例：0101 | 1100 = 1101。</p>
<h2 id="2-3-非运算"><a href="#2-3-非运算" class="headerlink" title="2.3 非运算"></a>2.3 非运算</h2><p>非运算，又称为逻辑取反，常用表示：<del>。示例：</del>0101 = 1010。</p>
<h2 id="2-4-异或运算"><a href="#2-4-异或运算" class="headerlink" title="2.4 异或运算"></a>2.4 异或运算</h2><p>异或运算，又称为半加运算，常用表示：^、XOR。示例：1101 ^ 1111 = 0010。</p>
<h2 id="2-5-位移运算"><a href="#2-5-位移运算" class="headerlink" title="2.5 位移运算"></a>2.5 位移运算</h2><p>左移运算,常用表示6 &lt;&lt; 1 = 12, 即二进制00000110向左移1位00001100。</p>
<p>右移运算分为无符号右移(&lt;&lt;&lt;)与有符号又移(&lt;&lt;)，6 &gt;&gt;&gt; 1 = 3,即二进制00000110向右移1位00000011。</p>
<h1 id="3-常见算法"><a href="#3-常见算法" class="headerlink" title="3. 常见算法"></a>3. 常见算法</h1><h2 id="3-1-求十进制的二进制数"><a href="#3-1-求十进制的二进制数" class="headerlink" title="3.1 求十进制的二进制数"></a>3.1 求十进制的二进制数</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 给一个十进制，打印其32位二进制</span></span><br><span class="line"><span class="comment"> *   思路： 将1移动i位，从左侧最高位进行&amp;运算，若结果为0，那么是当前位就是0；若结果为1，那么当前位就是1</span></span><br><span class="line"><span class="comment"> *   结果： 十进制数:6,转化二进制数为:00000000000000000000000000000110</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> num</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">printBinary</span><span class="params">(Integer num)</span> &#123;</span><br><span class="line">    <span class="type">StringBuilder</span> <span class="variable">bin</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">StringBuilder</span>();</span><br><span class="line">    <span class="comment">// 最高位为31位</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">31</span>; i &gt;= <span class="number">0</span> ; i--) &#123;</span><br><span class="line">        bin.append((num &amp; (<span class="number">1</span> &lt;&lt; i)) == <span class="number">0</span> ? <span class="string">&quot;0&quot;</span> : <span class="string">&quot;1&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    System.out.println(String.format(<span class="string">&quot;十进制数:%d,转化二进制数为:%s&quot;</span>, num, bin));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="3-2-不用额外变量交换两个整数的值"><a href="#3-2-不用额外变量交换两个整数的值" class="headerlink" title="3.2 不用额外变量交换两个整数的值"></a>3.2 不用额外变量交换两个整数的值</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 不用额外变量交换两个整数的值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> a 数值a</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> b 数值b</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">swap</span><span class="params">( Integer a, Integer b)</span> &#123;</span><br><span class="line">    System.out.println(<span class="string">&quot;交换前：a = &quot;</span> + a + <span class="string">&quot;, b = &quot;</span> + b);</span><br><span class="line">    <span class="comment">// 1.假设a异或b的结果为c，c就是a整数位信息和b整数位信息的所有不同信息。比如：a=4=0100，b=3=0011，c = a^b = 0111 = 7 = a,a变为了c，b还是b。</span></span><br><span class="line">    a = a ^ b;</span><br><span class="line">    <span class="comment">// 2.此时a = c = 7 = 0111,b = 3 = 0011，那么b = c ^ b  = a ^ b = 7 ^ 3 = 0111 ^ 0011 = 0100 = 4，a仍为c，b变为了a。</span></span><br><span class="line">    b = a ^ b;</span><br><span class="line">    <span class="comment">// 3.此时a = c = 7 = 0111,b = 4 = 0100，那么a = c ^ b = a ^ b = 7 ^ 4 = 0111 ^ 0100 = 0011 = 3，a变成了b，b仍然为a。做到了a和b的交换</span></span><br><span class="line">    a = a ^ b;</span><br><span class="line">    System.out.println(<span class="string">&quot;交换后：a = &quot;</span> + a + <span class="string">&quot;, b = &quot;</span> + b);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="3-3-不用加减乘除运算符计算两个整数的值"><a href="#3-3-不用加减乘除运算符计算两个整数的值" class="headerlink" title="3.3 不用加减乘除运算符计算两个整数的值"></a>3.3 不用加减乘除运算符计算两个整数的值</h2><p><img src="https://ltyeamin.github.io/imgs/2022/05/20220514140857.png"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 力扣：https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/</span></span><br><span class="line"><span class="comment"> * 用位运算实现两个数相加</span></span><br><span class="line"><span class="comment"> *   要求：不能使用+运算符</span></span><br><span class="line"><span class="comment"> *  5 + 6 = 11 = a + b = c + e</span></span><br><span class="line"><span class="comment"> * ==============================</span></span><br><span class="line"><span class="comment"> *      0000 0101  = 5 = a</span></span><br><span class="line"><span class="comment"> *      0000 0110  = 6 = b</span></span><br><span class="line"><span class="comment"> *  -----------------</span></span><br><span class="line"><span class="comment"> *  ^   0000 0011  = 3 = c</span></span><br><span class="line"><span class="comment"> *  &amp;   0000 0100  = 4 = d</span></span><br><span class="line"><span class="comment"> * &amp;&lt;&lt;1 0000 1000  = 8 = e</span></span><br><span class="line"><span class="comment"> * a+b  0000 1011  = 11 = c + e</span></span><br><span class="line"><span class="comment"> * ==============================</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> a</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> b</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">plus</span><span class="params">(Integer a, Integer b)</span> &#123;</span><br><span class="line">    <span class="comment">// 一直让b左移，当进位为0时停止</span></span><br><span class="line">   <span class="type">int</span> e;</span><br><span class="line">   <span class="keyword">while</span> (b != <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// 求a和b的进位和e</span></span><br><span class="line">        e = (a &amp; b) &lt;&lt; <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 求a和b的无进位和(异或)c</span></span><br><span class="line">        a ^= b;</span><br><span class="line">        <span class="comment">// b为进位</span></span><br><span class="line">        b = e;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 返回最终的a</span></span><br><span class="line">    <span class="keyword">return</span> a;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 和上述思路一样，只是不同的写法</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> a</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> b</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">plus</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b)</span> &#123;</span><br><span class="line">    <span class="comment">// 一直让b左移，当进位为0时停止</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">sum</span>  <span class="operator">=</span> a;</span><br><span class="line">    <span class="keyword">while</span> (b != <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// 将无进位和存放在sum里</span></span><br><span class="line">        sum = a ^ b;</span><br><span class="line">        <span class="comment">// 求进位和</span></span><br><span class="line">        b = (a &amp; b) &lt;&lt; <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 将每轮的和存放在sum里</span></span><br><span class="line">        a = sum;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 返回最终的a</span></span><br><span class="line">    <span class="keyword">return</span> sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">    * 用位运算实现两个数相减：利用加法实现减法</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> a</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> b</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">sub</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b)</span> &#123;</span><br><span class="line">       <span class="keyword">return</span> plus(a, negNumber(b));</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="comment">/**</span></span><br><span class="line"><span class="comment">    * 给一个整数，取相反数(取反+1) = 反码 + 1 = 补码</span></span><br><span class="line"><span class="comment">    *   原由： 不能使用加法(+)符号</span></span><br><span class="line"><span class="comment">    *   -6 = 6的反码+1 = ~6+1</span></span><br><span class="line"><span class="comment">    * ===========================</span></span><br><span class="line"><span class="comment">    *     0000 0110</span></span><br><span class="line"><span class="comment">    * ~   1111 1001</span></span><br><span class="line"><span class="comment">    *     0000 0001</span></span><br><span class="line"><span class="comment">    * ~+1 1111 1010</span></span><br><span class="line"><span class="comment">    * ===========================</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> num</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">negNumber</span><span class="params">(<span class="type">int</span> num)</span> &#123;</span><br><span class="line">       <span class="keyword">return</span> plus(~num,<span class="number">1</span>);</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 用位运算实现两个数相减：利用加法实现做乘法</span></span><br><span class="line"><span class="comment"> *   5 * 6 = 30  = 15 * 2 = 二进制的11110 (数学列算式方式推导出来的)</span></span><br><span class="line"><span class="comment"> * =======================================</span></span><br><span class="line"><span class="comment"> *   5    0000 0110</span></span><br><span class="line"><span class="comment"> *   6    0000 0101</span></span><br><span class="line"><span class="comment"> *  5*6   00000000 +  00001100 + 00000000 + 00011000 + ....... + 00000000</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> a</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> b</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">long</span> <span class="title function_">multiply</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b)</span> &#123;</span><br><span class="line">    <span class="type">int</span> <span class="variable">res</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 一直让b左移，当进位为0时停止</span></span><br><span class="line">    <span class="keyword">while</span> (b != <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// 判断当前b的最低位是否有1，若有1的话，累加a，若最低位是0，那么累加0，没意义所以跳过</span></span><br><span class="line">        <span class="keyword">if</span> ((b &amp; <span class="number">1</span>) != <span class="number">0</span>) &#123;</span><br><span class="line">            res = plus(res,a);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// a往左移1位</span></span><br><span class="line">        a &lt;&lt;= <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// b无符号右移1位，这里必须是无符号右移，不然死循环</span></span><br><span class="line">        b &gt;&gt;&gt;= <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="3-4-判断1个数是否是2或4的幂次方"><a href="#3-4-判断1个数是否是2或4的幂次方" class="headerlink" title="3.4 判断1个数是否是2或4的幂次方"></a>3.4 判断1个数是否是2或4的幂次方</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 题目：给一个int类型的数，判断该数是否为2的幂次方。</span></span><br><span class="line"><span class="comment"> * 思路：二进制除过最高位是1，其余位是0，那么就是2的幂次方。比如：1000=8,1000000=64</span></span><br><span class="line"><span class="comment"> * 转化：判断一个数的二进制，除了最高位为1，是否还有别的1存在</span></span><br><span class="line"><span class="comment"> * 结论：对于N为2的幂的数，都有 N&amp;(N-1)=0。比如：8&amp;(8-1) == 1000 &amp; 0111 = 0</span></span><br><span class="line"><span class="comment"> * 力扣：https://leetcode.cn/problems/power-of-two/description/</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> n</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span>  <span class="title function_">isPowerOfTwo</span><span class="params">(<span class="type">int</span> n)</span> &#123;</span><br><span class="line">    <span class="comment">// 方式一: JDK中Integer.bitCount统计1的个数，若只有1个，那么就是2的幂次方</span></span><br><span class="line">    <span class="comment">// return n &gt; 0 &amp;&amp; Integer.bitCount(n) == 1;</span></span><br><span class="line">    <span class="comment">// 方式二：与前一个数(全为1)进行与运算，那么就是2的幂次方</span></span><br><span class="line">    <span class="comment">// return n &gt; 0 &amp;&amp; (n &amp; (n - 1)) == 0;</span></span><br><span class="line">    <span class="comment">// 方式三: 当前数与当前数的相反数(补码)进行与运算后还是自己，那么就是2的幂次方，4=0000 0000 0000 0100， -4 = 1111 1111 1111 1100</span></span><br><span class="line">    <span class="comment">// return n &gt; 0 &amp;&amp; (n &amp; -n) == n;</span></span><br><span class="line">    <span class="comment">// 方式四:只需要判断n是否是 2^30的约数即可</span></span><br><span class="line">    <span class="keyword">return</span> n &gt; <span class="number">0</span> &amp;&amp;  (<span class="number">1</span> &lt;&lt; <span class="number">30</span>) % n == <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 下面写法是错误的，因为6也满足以下条件</span></span><br><span class="line">    <span class="comment">// return n &gt; 0 &amp;&amp;  ((1 &lt;&lt; 30) &amp; n) == 0;</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 题目：给一个int类型的数，判断该数是否为4的幂次方。</span></span><br><span class="line"><span class="comment"> * 思路：在二进制表示中有且只有一个奇数位为1，那么就是4的幂次方。比如：100=4,10000=16,1000000=64</span></span><br><span class="line"><span class="comment"> * 力扣：https://leetcode.cn/problems/power-of-four/submissions/</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> n</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span>  <span class="title function_">isPowerOfFour</span><span class="params">(<span class="type">int</span> n)</span> &#123;</span><br><span class="line">    <span class="comment">// 可以用正则四进制匹配二进制都可以处理</span></span><br><span class="line">    <span class="comment">// return Integer.toString(n, 4).matches(&quot;10*&quot;);</span></span><br><span class="line">    <span class="comment">// 可以用正则四进制匹配二进制都可以处理</span></span><br><span class="line">    <span class="comment">// String bin = Integer.toString(n, 2);</span></span><br><span class="line">    <span class="comment">// return bin.length() % 2 !=0 &amp;&amp; bin.matches(&quot;10*&quot;);</span></span><br><span class="line">    <span class="keyword">return</span> n &gt; <span class="number">0</span> &amp;&amp; (n &amp; (n - <span class="number">1</span>)) == <span class="number">0</span> &amp;&amp; (n &amp; <span class="number">0b01010101010101010101010101010101</span>) != <span class="number">0</span> ;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</section>
    <!-- Tags START -->
    
      <div class="tags">
        <span>Tags:</span>
        
  <a href="/tags#算法" >
    <span class="tag-code">算法</span>
  </a>

      </div>
    
    <!-- Tags END -->
    <!-- NAV START -->
    
  <div class="nav-container">
    <!-- reverse left and right to put prev and next in a more logic postition -->
    
      <a class="nav-left" href="/2022/01/23/%E3%80%90%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E3%80%91%E4%B8%8D%E7%9F%A5%E6%89%80%E6%8E%AA%E7%9A%84%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/">
        <span class="nav-arrow">← </span>
        
          【数据结构与算法】不知所措的二分查找
        
      </a>
    
    
      <a class="nav-right" href="/2022/05/07/Zookeeper%E4%B8%93%E9%A2%98-Zookeeper%E5%85%A5%E9%97%A8/">
        
          Zookeeper专题-Zookeeper入门
        
        <span class="nav-arrow"> →</span>
      </a>
    
  </div>

    <!-- NAV END -->
    <!-- 打赏 START -->
    
      <div class="money-like">
        <div class="reward-btn">
          赏
          <span class="money-code">
            <span class="alipay-code">
              <div class="code-image"></div>
              <b>使用支付宝打赏</b>
            </span>
            <span class="wechat-code">
              <div class="code-image"></div>
              <b>使用微信打赏</b>
            </span>
          </span>
        </div>
        <p class="notice">若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏</p>
      </div>
    
    <!-- 打赏 END -->
    <!-- 二维码 START -->
    
      <div class="qrcode">
        <canvas id="share-qrcode"></canvas>
        <p class="notice">扫描二维码，分享此文章</p>
      </div>
    
    <!-- 二维码 END -->
    
      <!-- Utterances START -->
      <div id="utterances"></div>
      <script src="https://utteranc.es/client.js"
        repo="ltyeamin/blogtalks"
        issue-term="pathname"
        theme="github-light"
        crossorigin="anonymous"
        async></script>    
      <!-- Utterances END -->
    
  </article>
  <!-- Article END -->
  <!-- Catalog START -->
  
    <aside class="catalog-container">
  <div class="toc-main">
    <strong class="toc-title">Catalog</strong>
    
      <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#1-%E6%95%B0%E6%8D%AE%E8%A1%A8%E7%A4%BA%E4%B8%8E%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%8C%96"><span class="toc-nav-text">1. 数据表示与进制转化</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#1-1-%E6%95%B0%E6%8D%AE%E8%A1%A8%E7%A4%BA"><span class="toc-nav-text">1.1 数据表示</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-1-1-%E5%8D%81%E8%BF%9B%E5%88%B6"><span class="toc-nav-text">1.1.1 十进制</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-1-2-%E4%BA%8C%E8%BF%9B%E5%88%B6"><span class="toc-nav-text">1.1.2 二进制</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-1-3-%E5%85%AB%E8%BF%9B%E5%88%B6"><span class="toc-nav-text">1.1.3 八进制</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-1-4-%E5%8D%81%E5%85%AD%E8%BF%9B%E5%88%B6"><span class="toc-nav-text">1.1.4 十六进制</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#1-2-%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%8C%96"><span class="toc-nav-text">1.2 进制转化</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-2-1-%E5%8D%81%E8%BF%9B%E5%88%B6%E4%B8%8E%E4%BA%8C%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%8C%96"><span class="toc-nav-text">1.2.1 十进制与二进制转化</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-2-2-%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%8E%E5%85%AB%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%8C%96"><span class="toc-nav-text">1.2.2 二进制与八进制转化</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-2-3-%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%8E%E5%8D%81%E5%85%AD%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%8C%96"><span class="toc-nav-text">1.2.3 二进制与十六进制转化</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-2-4-%E5%9B%9B%E7%A7%8D%E7%A0%81%E5%88%B6"><span class="toc-nav-text">1.2.4 四种码制</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#1-2-5-%E5%B8%B8%E7%94%A8%E6%95%B0%E5%80%BC"><span class="toc-nav-text">1.2.5 常用数值</span></a></li></ol></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#2-%E5%B8%B8%E8%A7%81%E4%BD%8D%E8%BF%90%E7%AE%97"><span class="toc-nav-text">2. 常见位运算</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#2-1-%E4%B8%8E%E8%BF%90%E7%AE%97"><span class="toc-nav-text">2.1 与运算</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#2-2-%E6%88%96%E8%BF%90%E7%AE%97"><span class="toc-nav-text">2.2 或运算</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#2-3-%E9%9D%9E%E8%BF%90%E7%AE%97"><span class="toc-nav-text">2.3 非运算</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#2-4-%E5%BC%82%E6%88%96%E8%BF%90%E7%AE%97"><span class="toc-nav-text">2.4 异或运算</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#2-5-%E4%BD%8D%E7%A7%BB%E8%BF%90%E7%AE%97"><span class="toc-nav-text">2.5 位移运算</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#3-%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95"><span class="toc-nav-text">3. 常见算法</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#3-1-%E6%B1%82%E5%8D%81%E8%BF%9B%E5%88%B6%E7%9A%84%E4%BA%8C%E8%BF%9B%E5%88%B6%E6%95%B0"><span class="toc-nav-text">3.1 求十进制的二进制数</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#3-2-%E4%B8%8D%E7%94%A8%E9%A2%9D%E5%A4%96%E5%8F%98%E9%87%8F%E4%BA%A4%E6%8D%A2%E4%B8%A4%E4%B8%AA%E6%95%B4%E6%95%B0%E7%9A%84%E5%80%BC"><span class="toc-nav-text">3.2 不用额外变量交换两个整数的值</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#3-3-%E4%B8%8D%E7%94%A8%E5%8A%A0%E5%87%8F%E4%B9%98%E9%99%A4%E8%BF%90%E7%AE%97%E7%AC%A6%E8%AE%A1%E7%AE%97%E4%B8%A4%E4%B8%AA%E6%95%B4%E6%95%B0%E7%9A%84%E5%80%BC"><span class="toc-nav-text">3.3 不用加减乘除运算符计算两个整数的值</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#3-4-%E5%88%A4%E6%96%AD1%E4%B8%AA%E6%95%B0%E6%98%AF%E5%90%A6%E6%98%AF2%E6%88%964%E7%9A%84%E5%B9%82%E6%AC%A1%E6%96%B9"><span class="toc-nav-text">3.4 判断1个数是否是2或4的幂次方</span></a></li></ol></li></ol>
    
  </div>
</aside>
  
  <!-- Catalog END -->
</main>

<script>
  (function () {
    var url = 'http://example.com/2022/05/02/【数据结构与算法】高效的位运算/';
    var banner = ''
    if (banner !== '' && banner !== 'undefined' && banner !== 'null') {
      $('#article-banner').css({
        'background-image': 'url(' + banner + ')'
      })
    } else {
      $('#article-banner').geopattern(url)
    }
    $('.header').removeClass('fixed-header')

    // error image
    $(".markdown-content img").on('error', function() {
      $(this).attr('src', '/css/images/error_icon.png')
      $(this).css({
        'cursor': 'default'
      })
    })

    // zoom image
    $(".markdown-content img").on('click', function() {
      var src = $(this).attr('src')
      if (src !== '/css/images/error_icon.png') {
        var imageW = $(this).width()
        var imageH = $(this).height()

        var zoom = ($(window).width() * 0.95 / imageW).toFixed(2)
        zoom = zoom < 1 ? 1 : zoom
        zoom = zoom > 2 ? 2 : zoom
        var transY = (($(window).height() - imageH) / 2).toFixed(2)

        $('body').append('<div class="image-view-wrap"><div class="image-view-inner"><img src="'+ src +'" /></div></div>')
        $('.image-view-wrap').addClass('wrap-active')
        $('.image-view-wrap img').css({
          'width': `${imageW}`,
          'transform': `translate3d(0, ${transY}px, 0) scale3d(${zoom}, ${zoom}, 1)`
        })
        $('html').css('overflow', 'hidden')

        $('.image-view-wrap').on('click', function() {
          $(this).remove()
          $('html').attr('style', '')
        })
      }
    })
  })();
</script>


  <script>
    var qr = new QRious({
      element: document.getElementById('share-qrcode'),
      value: document.location.href
    });
  </script>






    <div class="scroll-top">
  <span class="arrow-icon"></span>
</div>
    <footer class="app-footer">
  <p class="copyright">
    &copy; 2024 | Proudly powered by <a href="https://hexo.io" target="_blank">Hexo</a>
    <br>
    Theme by <a target="_blank" rel="noopener" href="https://github.com/ltyeamin">tong.li</a>
  </p>
</footer>

<script>
  function async(u, c) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }
</script>
<script>
  async("https://cdn.staticfile.org/fastclick/1.0.6/fastclick.min.js", function(){
    FastClick.attach(document.body);
  })
</script>

<script>
  var hasLine = 'true';
  async("https://cdn.staticfile.org/highlight.js/9.12.0/highlight.min.js", function(){
    $('figure pre').each(function(i, block) {
      var figure = $(this).parents('figure');
      if (hasLine === 'false') {
        figure.find('.gutter').hide();
      }
      hljs.configure({useBR: true});
      var lang = figure.attr('class').split(' ')[1] || 'code';
      var codeHtml = $(this).html();
      var codeTag = document.createElement('code');
      codeTag.className = lang;
      codeTag.innerHTML = codeHtml;
      $(this).attr('class', '').empty().html(codeTag);
      figure.attr('data-lang', lang.toUpperCase());
      hljs.highlightBlock(block);
    });
  })
</script>
<!-- Baidu Tongji -->



<script src='https://cdn.staticfile.org/mermaid/8.11.2/mermaid.min.js'></script>



<script src="/js/script.js"></script>


  </body>
</html>